home *** CD-ROM | disk | FTP | other *** search
/ IRIX Base Documentation 2001 May / SGI IRIX Base Documentation 2001 May.iso / usr / share / catman / p_man / cat3 / complib / fft.z / fft
Encoding:
Text File  |  1998-10-30  |  11.9 KB  |  265 lines
  1.  
  2.  
  3.  
  4. FFFFFFFFTTTT((((3333FFFF))))                                                                FFFFFFFFTTTT((((3333FFFF))))
  5.  
  6.  
  7.  
  8. NNNNAAAAMMMMEEEE
  9.      FFT, libfft - libcomplib.sgimath - Fast Fourier Transforms
  10.  
  11. DDDDEEEESSSSCCCCRRRRIIIIPPPPTTTTIIIIOOOONNNN
  12.      A set of Fast Fourier Transform (FFT) modules, fully optimized for SGI
  13.      computers. On parallel systems, Multi Dimensional FFTs, as well as large
  14.      1D transforms are computed in parallel. The FFT modules are provided with
  15.      both a C and a Fortran interface. They are part of the complib.sgimath
  16.      library.
  17.  
  18.      These modules include:
  19.      - One, multiple one, two and three dimensional FFTs, real to complex,
  20.      complex to real and complex to complex, in single and double precision.
  21.      - Scaling routines.
  22.      - Fourier Product routines.
  23.  
  24.  
  25. CCCC iiiinnnntttteeeerrrrffffaaaacccceeee
  26.      For the C interface two types "complex" and "zomplex" have been defined
  27.      as structures of two floating point variables ( re, im ).  They are
  28.      equivalent to the "complex" and "double complex" Fortran types.
  29.  
  30.                typedef struct {
  31.                    float re;
  32.                    float im;  } complex;
  33.  
  34.                typedef struct {
  35.                    double re;
  36.                    double im; } zomplex;
  37.  
  38.      These types as well as the prototypes of the different functions for FFTs
  39.      are defined in the "/usr/include/fft.h" header file.
  40.  
  41.  
  42.      In C, _M_u_l_t_i _D_i_m_e_n_s_i_o_n_a_l _s_e_q_u_e_n_c_e_s are actually stored into a 1D array
  43.      (contiguous data). For example, an MxN 2D sequence must be stored into an
  44.      array of size LxN (M <= L), and the sample at index (i,j) is actually
  45.      stored as element Array[i+L*j] -
  46.  
  47.  
  48. NNNNAAAAMMMMIIIINNNNGGGG CCCCOOOONNNNVVVVEEEENNNNTTTTIIIIOOOONNNNSSSS
  49.      _I_n_i_t_i_a_l_i_z_a_t_i_o_n - ccccfffffffftttt____ddddiiii,,,, zzzzfffffffftttt____ddddiiii,,,, ssssfffffffftttt____dddduuuuiiii,,,, ddddfffffffftttt____dddduuuuiiii::::
  50.      initialize the twiddle factors needed for the FFT computation, e.g.
  51.      cfft1di.
  52.  
  53.      _C_o_m_p_u_t_a_t_i_o_n -
  54.      ccccfffffffftttt____dddd,,,, zzzzfffffffftttt____dddd ::::
  55.       compute the Direct Fourier Transform or the Inverse Fourier Transform
  56.      complex data, e.g. zfft2d.
  57.      ssssccccfffffffftttt____dddduuuu,,,, ddddzzzzfffffffftttt____dddduuuu ::::
  58.       Direct Fourier Transform of a real array input. Although the transform
  59.      is performed in place, the output is to be considered as an array of
  60.  
  61.  
  62.  
  63.                                                                         PPPPaaaaggggeeee 1111
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70. FFFFFFFFTTTT((((3333FFFF))))                                                                FFFFFFFFTTTT((((3333FFFF))))
  71.  
  72.  
  73.  
  74.      complex data, e.g. scfftm1du.
  75.      ccccssssfffffffftttt____dddduuuu,,,, zzzzddddfffffffftttt____dddduuuu :::: Inverse Fourier Transform for a real value sequence.
  76.       Although the transform is performed in place, the input is taken as a
  77.      Complex value sequence, while the ouput is a real sequence. (e.g.
  78.      zdfft1du).
  79.  
  80.      _F_o_u_r_i_e_r _P_r_o_d_u_c_t - ccccpppprrrroooodddd____dddd,,,, zzzzpppprrrroooodddd____dddd,,,, sssspppprrrroooodddd____dddduuuu,,,, ddddpppprrrroooodddd____dddduuuu::::
  81.      in place product of the Fourier Transform of a sequence with the Fourier
  82.      Transform of a filter, e.g. cprod3d .
  83.      (The product of the two Fourier Transforms is equal to the tranform of
  84.      the convolution of the two corresponding sequences.)
  85.  
  86.  
  87.      _S_c_a_l_i_n_g - ssssssssccccaaaallll____dddduuuu,,,, ddddssssccccaaaallll____dddduuuu,,,, ccccssssccccaaaallll____dddd,,,, zzzzssssccccaaaallll____dddd ::::
  88.      Scales the sequence by a real value, e.g. dscal2du . This may be usefull
  89.      as the FFTs are not normalized and after a double call( direct-transform,
  90.      inverse-transform) the final output is equal to the input scaled by the
  91.      number of samples.
  92.  
  93. SSSSUUUUMMMMMMMMAAAARRRRYYYY
  94.      NNNNOOOOTTTTEEEE:::: The Development Magic (-o32) FFT library differs from the -n32/-64
  95.      FFT library.  The -o32 FFT library contains only a subset of the routines
  96.      in the -n32/-64 library.  See the o32fft man page for details.
  97.  
  98.      FFFFuuuunnnnccccttttiiiioooonnnnssss aaaannnndddd RRRRoooouuuuttttiiiinnnneeeessss::::
  99.       -----------------------------------------------------------------------
  100.      |             |             |  Multiple   |              |              |
  101.      |             | 1 Dimension | 1 Dimension | 2 Dimensions | 3 Dimensions |
  102.      |             |             |             |              |              |
  103.       -----------------------------------------------------------------------
  104.      |    REAL     |  scfft1dui  |  scfftm1dui |   scfft2dui  |   scfft3dui  |
  105.      |     to      |  scfft1du   |  scfftm1du  |   scfft2du   |   scfft3du   |
  106.      |   COMPLEX   |  csfft1du   |  csfftm1du  |   csfft2du   |   csfft3du   |
  107.      |             |  sprod1du   |  sprodm1du  |   sprod2du   |   sprod3du   |
  108.      |   Single    |  sscal1d    |  sscalm1d   |   sscal2d    |   sscal3d    |
  109.      |  Precision  |             |             |              |              |
  110.       -----------------------------------------------------------------------
  111.      |    REAL     |  dzfft1dui  |  dzfftm1dui |   dzfft2dui  |   dzfft3dui  |
  112.      |     to      |  dzfft1du   |  dzfftm1du  |   dzfft2du   |   dzfft3du   |
  113.      |   COMPLEX   |  zdfft1du   |  zdfftm1du  |   zdfft2du   |   zdfft3du   |
  114.      |             |  dprod1du   |  dprodm1du  |   dprod2du   |   dprod3du   |
  115.      |   Double    |  dscal1d    |  dscalm1d   |   dscal2d    |   dscal3d    |
  116.      |  Precision  |             |             |              |              |
  117.       -----------------------------------------------------------------------
  118.      |   COMPLEX   |             |             |              |              |
  119.      |     to      |  cfft1di    |  cfftm1di   |   cfft2di    |   cfft3di    |
  120.      |   COMPLEX   |  cfft1d     |  cfftm1d    |   cfft2d     |   cfft3d     |
  121.      |             |  cprod1d    |  cprodm1d   |   cprod2d    |   cprod3d    |
  122.      |   Single    |  cscal1d    |  cscalm1d   |   cscal2d    |   cscal3d    |
  123.      |  Precision  |             |             |              |              |
  124.       -----------------------------------------------------------------------
  125.      |  COMPLEX    |             |             |              |              |
  126.  
  127.  
  128.  
  129.                                                                         PPPPaaaaggggeeee 2222
  130.  
  131.  
  132.  
  133.  
  134.  
  135.  
  136. FFFFFFFFTTTT((((3333FFFF))))                                                                FFFFFFFFTTTT((((3333FFFF))))
  137.  
  138.  
  139.  
  140.      |    to       |  zfft1di    |  zfftm1di   |   zfft2di    |   zfft3di    |
  141.      |  COMPLEX    |  zfft1d     |  zfftm1d    |   zfft2d     |   zfft3d     |
  142.      |             |  zprod1d    |  zprodm1d   |   zprod2d    |   zprod3d    |
  143.      |   Double    |  zscal1d    |  zscalm1d   |   zscal2d    |   zscal3d    |
  144.      |  Precision  |             |             |              |              |
  145.       -----------------------------------------------------------------------
  146.  
  147.  
  148. LLLLIIIINNNNKKKKIIIINNNNGGGG wwwwiiiitttthhhh ccccoooommmmpppplllliiiibbbb....ssssggggiiiimmmmaaaatttthhhh
  149.      _C _p_r_o_g_r_a_m_s:
  150.      for serial binaries
  151.           cccccccc ----oooo mmmmyyyy____eeeexxxxeeee mmmmyyyy____ssssoooouuuurrrrcccceeee....cccc ----llllccccoooommmmpppplllliiiibbbb....ssssggggiiiimmmmaaaatttthhhh
  152.      for parallel executables
  153.           cccccccc ----oooo mmmmyyyy____ppppaaaarrrraaaalllllllleeeellll____eeeexxxxeeee mmmmyyyy____ssssoooouuuurrrrcccceeee....cccc ----llllccccoooommmmpppplllliiiibbbb....ssssggggiiiimmmmaaaatttthhhh____mmmmpppp ----mmmmpppp
  154.  
  155.      _F_o_r_t_r_a_n _p_r_o_g_r_a_m_s:
  156.      for serial binaries
  157.           ffff77777777 ----oooo mmmmyyyy____eeeexxxxeeee mmmmyyyy____ssssoooouuuurrrrcccceeee....ffff ----llllccccoooommmmpppplllliiiibbbb....ssssggggiiiimmmmaaaatttthhhh
  158.      for parallel executables
  159.           ffff77777777 ----oooo mmmmyyyy____ppppaaaarrrraaaalllllllleeeellll____eeeexxxxeeee mmmmyyyy____ssssoooouuuurrrrcccceeee....ffff ----llllccccoooommmmpppplllliiiibbbb....ssssggggiiiimmmmaaaatttthhhh____mmmmpppp ----mmmmpppp
  160.  
  161.  
  162. PPPPEEEERRRRFFFFOOOORRRRMMMMAAAANNNNCCCCEEEE
  163.      To be _F_a_s_t the _F_a_s_t _F_o_u_r_i_e_r _T_r_a_n_s_f_o_r_m relies on the factorization of the
  164.      array size into small prime factors. The smaller the factors, the lesser
  165.      the floating point operations required. E.g. a 1D Fourier transform of
  166.      size 899(29*31) is much more expensive to compute than one of size
  167.      900(2*2*3*3*5*5), (roughly ten times more floating point operations).
  168.  
  169.      To boost performance special code exists for Radices 2, 3, 4 and 5. Note,
  170.      the radix 4 is equivallent to a double radix 2 implementation, but it
  171.      reduces computation cost by 15%.
  172.  
  173.      For Multiple 1D, or 2D or 3D FFTs, although the same computation could be
  174.      performed using 1D FFTs in a loop, the corresponding modules are more
  175.      efficient as they involve less overhead, and as the individual 1D FFTs
  176.      can be pipelined together.
  177.  
  178.      Furthermore, the Multiple 1D, or 2D or 3D modules are parallel, thus
  179.      enabling another performance level increase without any work in the user
  180.      source.
  181.  
  182. SSSSEEEEEEEE AAAALLLLSSSSOOOO
  183.      o32fft
  184.  
  185.      cfft1d, cfftm1d, cfft2d, cfft3d, cfft1di, cfftm1di, cfft2di, cfft3di,
  186.      zfft1d, zfftm1d, zfft2d, zfft3d, zfft1di, zfftm1di, zfft2di, zfft3di,
  187.      scfft1du, csfft1du, scfft1dui, dzfft1du, zdfft1du, dzfft1dui,
  188.      scfftm1du, csfftm1du, scfftm1dui, dzfftm1du, zdfftm1du, dzfftm1dui,
  189.      scfft2du, csfft2du, scfft2dui, dzfft2du, zdfft2du, dzfft2dui,
  190.      scfft3du, csfft3du, scfft3dui, dzfft3du, zdfft3du, dzfft3dui,
  191.  
  192.  
  193.  
  194.  
  195.                                                                         PPPPaaaaggggeeee 3333
  196.  
  197.  
  198.  
  199.  
  200.  
  201.  
  202. FFFFFFFFTTTT((((3333FFFF))))                                                                FFFFFFFFTTTT((((3333FFFF))))
  203.  
  204.  
  205.  
  206.      cprod1d, zprod1d, sprod1du, dprod1du,
  207.      cprodm1d, zprodm1d, sprodm1du, dprodm1du,
  208.      cprod2d, zprod2d, sprod2du, dprod2du,
  209.      cprod3d, zprod3d, sprod3du, dprod3du,
  210.  
  211.      cscal1d, zscal1d, sscal1d, dscal1d,
  212.      cscalm1d, zscalm1d, sscalm1d, dscalm1d,
  213.      cscal2d, zscal2d, sscal2d, dscal2d,
  214.      cscal3d, zscal3d, sscal3d, dscal3d
  215.  
  216.  
  217.  
  218.  
  219.  
  220.  
  221.  
  222.  
  223.  
  224.  
  225.  
  226.  
  227.  
  228.  
  229.  
  230.  
  231.  
  232.  
  233.  
  234.  
  235.  
  236.  
  237.  
  238.  
  239.  
  240.  
  241.  
  242.  
  243.  
  244.  
  245.  
  246.  
  247.  
  248.  
  249.  
  250.  
  251.  
  252.  
  253.  
  254.  
  255.  
  256.  
  257.  
  258.                                                                         PPPPaaaaggggeeee 4444
  259.  
  260.  
  261.  
  262.  
  263.  
  264.  
  265.